|
Jupyter at Bryn Mawr College |
|
|
| Public notebooks: /services/public/dblank / CS240 Computer Organization / 2015-Fall / Notes | |||
1. Representing Information¶
How do we represent data in a computer?
At the lowest level, a computer is an electronic machine.
- works by controlling the flow of electrons
Easy to recognize two conditions:
- presence of a voltage - we'll call this state "1"
- absence of a voltage - we'll call this state "0"
Could base state on value of voltage, but control and detection circuits more complex.
- compare turning on a light switch to
- measuring or regulating voltage
2. Representing numbers in different bases¶
2.1 Positional number systems¶
Consider these positions in a number system:
| n3 | n2 | n1 | n0 |
| d3 | d2 | d1 | d0 |
$$ d_3 \times n^3 + d_2 \times n^2 + d_1 \times n^1 + d_0 \times n^0 $$
Consider the number 350 in base 10 (radix 10). That is, n is 10, and thus:
$$ 0 \times n^3 + 3 \times n^2 + 5 \times n^1 + 0 \times n^0 $$
$$ 0 \times 1000 + 3 \times 100 + 5 \times 10 + 0 \times 1 $$
Consider the number 0110 in base 2 (radix 2). That is, n is 2, and thus:
$$ 0 \times n^3 + 1 \times n^2 + 1 \times n^1 + 0 \times n^0 $$
$$ 0 \times 8 + 1 \times 4 + 1 \times 2 + 0 \times 1 $$
or 6 in base 10.
2.2 Converting to base n¶
To convert a base 10 number to base n, use the following algorithm:
%%python
def rep(digit):
if digit <= 9:
return str(digit)
elif digit == 10:
return "A"
elif digit == 11:
return "B"
elif digit == 12:
return "C"
elif digit == 13:
return "D"
elif digit == 14:
return "E"
elif digit == 15:
return "F"
else:
return "?"
number = 4096 * 15 + 256 * 15 + 16 * 15 + 15
base = 16
positions = 4
print("%d in base %d is: " % (number, base))
for i in range(positions - 1, -1, -1):
digit = (number // base ** i)
number = number - digit * base ** i
print(rep(digit), end="")
%%python
print(bin(14))
3. Data Types¶
3.1 Integers¶
There are two categories of integers (whole numbers):
- Unsigned integers
- Typically, each bit represents decreasing (from left to right) magnitudes of powers of 2
- Signed integers
- Signed magnitude
- 1's complement
- 2's complement
Unsigned integers are all positive, and thus you can use all bits to represent positive numbers.
Signed integers use a bit to represent whether the integer is positive or negative.
3.1.1 Unsigned Integers¶
| Number | Bits |
|---|---|
| 0 | 0000 |
| 1 | 0001 |
| 2 | 0010 |
| 3 | 0011 |
| 4 | 0100 |
| 5 | 0101 |
| 6 | 0110 |
| 7 | 0111 |
| 8 | 1000 |
| 9 | 1001 |
| 10 | 1010 |
| 11 | 1011 |
| 12 | 1100 |
| 13 | 1101 |
| 14 | 1110 |
| 15 | 1111 |
What is the largest unsigned integer using 16 bits? Using 32 bits?
%%python
print(2 ** 4 - 1)
%%processing
println(pow(2, 4) - 1);
3.1.2 Signed Integers¶
Unsigned integers are nice and simple. But, for much of what we want our LC-3 to do might involve negative numbers.
How can we represent negative numbers?
It could be completely arbitrary... but we want to keep the circuits as simple as we can make them. So, it makes sense to have patterns that we can take advantage of.
3.1.2.1 Signed Magnitude¶
The simplest pattern (at least for humans) might be the "signed magnitude"... just use the left-most bit to mean negative.
| Number | Bits |
|---|---|
| -7 | 1111 |
| -6 | 1110 |
| -5 | 1101 |
| -4 | 1100 |
| -3 | 1011 |
| -2 | 1010 |
| -1 | 1001 |
| -0 | 1000 |
| 0 | 0000 |
| 1 | 0001 |
| 2 | 0010 |
| 3 | 0011 |
| 4 | 0100 |
| 5 | 0101 |
| 6 | 0110 |
| 7 | 0111 |
3.1.3 One's Complement¶
| Number | Bits |
|---|---|
| -7 | 1000 |
| -6 | 1001 |
| -5 | 1010 |
| -4 | 1011 |
| -3 | 1100 |
| -2 | 1101 |
| -1 | 1110 |
| -0 | 1111 |
| 0 | 0000 |
| 1 | 0001 |
| 2 | 0010 |
| 3 | 0011 |
| 4 | 0100 |
| 5 | 0101 |
| 6 | 0110 |
| 7 | 0111 |
However, we have to implement mathematics in a circuit (as we will see). We want that the Arithmetic and Logic Unit circuit to be able to add any two binary numbers and get the appropriate binary number.
What we want is that REPRESENTATION(a + b) == REPRESENTATION(a) + REPRESENTATION(b)
Problems with 1's complement and Signed magnitude:
- negative zero?
- 0001 + 1110 = 1111
- does 1111 == 0000? (one's complement); 1000 == 0000? (signed magnitude)
3.1.4 Two's Complement¶
| Number | Bits |
|---|---|
| -8 | 1000 |
| -7 | 1001 |
| -6 | 1010 |
| -5 | 1011 |
| -4 | 1100 |
| -3 | 1101 |
| -2 | 1110 |
| -1 | 1111 |
| 0 | 0000 |
| 1 | 0001 |
| 2 | 0010 |
| 3 | 0011 |
| 4 | 0100 |
| 5 | 0101 |
| 6 | 0110 |
| 7 | 0111 |
Consider:
- no negative zero
- 0111 + 1000 = 1111... correct?
Now, we have solved all of the negative zero issues.
What is the range of numbers represented in 16 bits using 2's complement?
3.2 Floating Point Numbers¶
Could be used just to indicate where a decimal place
Used to represent really big numbers and really small numbers.
Consider that we have 32 bits to use. The IEEE Standard for Floating Point Arithmetic defined the following representation:
- 1 bit for the sign (0 = positive, 1 = negative)
- 8 bits for exponent (offset by 127)
- 23 bits for precision (leading 1 assumed)
3.2.1 To IEEE format¶
Consider converting:
$$ -6 \dfrac{5}{8} $$
to IEEE floating-point representation.
3.2.1.1 Convert to binary representation¶
| n3 | n2 | n1 | n0 | Decimal | n-1 | n-2 | n-3 | n-4 | |
|---|---|---|---|---|---|---|---|---|---|
| d3 | d2 | d1 | d0 | . | d-1 | d-2 | d-3 | d-4 | |
Just as before we see how many column values will go into a number, we continue for $n^{-1}$...
$$ 0 \times n^3 + 1 \times n^2 + 1 \times n^1 + 0 \times n^0 + 1 \times n^{-1} + 0 \times n^{-2} + 1 \times n^{-3} $$
$$ 0 \times 8 + 1 \times 4 + 1 \times 2 + 0 \times 1 + 1 \times \dfrac{1}{2} + 0 \times \dfrac{1}{4} + 1 \times \dfrac{1}{8} $$
or:
-0110.101
3.2.1.2 Normalize¶
Move the decimal place to left or right to get a single 1 to the left of the decimal place. Count how many places and in which direction:
-0110.101
becomes:
-01.10101
with 2 moves (exponent).
3.2.1.3 Add 127 to exponent, convert to binary¶
2 + 127 = 129
which is:
100000001
in binary.
3.2.1.4 Combine, leaving off leading 1 of precision¶
1 100000001 10101
and pad to a total of 32 bits:
1 100000001 10101000000000000000000
3.2.2 From IEEE format¶
Consider:
00111101100000000000000000000000
Do the reverse:
3.2.2.1 First digit is sign¶
Break into parts:
0 01111011 00000000000000000000000
It is positive!
3.2.2.1 Next 8 bits is exponent, minus 127¶
Convert next 8 unsigned bits into decimal, and subtract 127:
01111011 is 123
123 - 127 = -4
3.2.2.1 Get precision¶
Put a one in front of the last 23 bits:
1.00000000000000000000000
and move the decimal spot by the exponent. In this case, 4 places to the left:
0.000100000000000000000000000
Convert to decimal:
$$ 0 * \dfrac{1}{2} + 0 * \dfrac{1}{4} + 0 * \dfrac{1}{8} + 1 * \dfrac{1}{16} ... $$
3.2.2.1 All together¶
$$
- \dfrac{1}{16} $$
%%python
for i in range(0, 10, .1):
print(i)